//
//  CLLinkedReverse.m
//  Charles
//
//  Created by Charles on 2020/3/16.
//  Copyright © 2020 charles. All rights reserved.
//

#import "CLLinkedReverse.h"


/*
 算法思想：头插法
 定义一个新的头结点指针NewH使它指向NULL，然后定义一个临时指针p，指向原链表的头结点，来遍历原链表，遍历中把临时指针移动到第二个位置，把新的头结点指针指向第一个节点。必须要先做p指针的移动。否则会导致原链表里面后面的部分丢失。后续遍历的话是先把p指针移动到下一个位置，再让NewH指针指向原链表中的第二个节点,顺次执行直到p指针指向NULL就结束了。
 */

@implementation CLLinkedReverse

// 构造链表
struct Node *constructList(void){
    // 头结点定义
    struct Node *head = NULL;
    // 记录当前尾节点
    struct Node *cur = NULL;
    
    for (int i = 1; i < 5; i++) {
        struct Node *node = malloc(sizeof(struct Node));
        node->data = i;
        
        // 头结点如果为空，则新节点就是头结点
        if (head == NULL) {
            head = node;
        }else {
            // 当前结点的next为新节点
            cur->next = node;
        }
        // 设置当前结点为新节点
        cur = node;
    }
    return head;
}
// 打印链表
void printList(struct Node *head){
    struct Node *currentNode = head;
    while(currentNode != NULL) {
        NSLog(@"data is %d",currentNode->data);
        currentNode = currentNode->next;
    }
}

// 反转链表
struct Node *reverseList(struct Node *head){
    // 反转后的链表头部
    struct Node *newHead = NULL;
    // 定义遍历指针，初始化为头结点
    struct Node *p = head;
    // 遍历链表
    while (p != NULL) {
        // 记录下一个结点
        struct Node *temp = p->next;
        // 当前结点的next指向新链表头部
        p->next = newHead;
        // 更改链表头部为当前结点
        newHead = p;
        // 移动p指针
        p = temp;
    }
    return newHead;
}


@end
